<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(B卷,200分)- 完全二叉树非叶子部分后序遍历（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>给定一个以顺序储存结构存储整数值的完全二叉树序列&#xff08;最多1000个整数&#xff09;&#xff0c;请找出此完全二叉树的所有非叶子节点部分&#xff0c;然后采用后序遍历方式将此部分树&#xff08;不包含叶子&#xff09;输出。</p> 
<p>1、只有一个节点的树&#xff0c;此节点认定为根节点&#xff08;非叶子&#xff09;。</p> 
<p>2、此完全二叉树并非满二叉树&#xff0c;可能存在倒数第二层出现叶子或者无右叶子的情况</p> 
<p>其他说明&#xff1a;二叉树的后序遍历是基于根来说的&#xff0c;遍历顺序为&#xff1a;左-右-根</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>一个通过空格分割的整数序列字符串</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>非叶子部分树结构。备注&#xff1a;输出数字以空格分隔</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">1 2 3 4 5 6 7</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">2 3 1</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">找到非叶子部分树结构&#xff0c;然后采用后序遍历输出。</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>完全二叉树定义</p> 
<blockquote> 
 <p>一棵深度为k的有n个结点的二叉树&#xff0c;对树中的结点按从上至下、从左到右的顺序进行编号&#xff0c;如果编号为i&#xff08;1≤i≤n&#xff09;的结点与满二叉树中编号为i的结点在二叉树中的位置相同&#xff0c;则这棵二叉树称为完全二叉树。</p> 
</blockquote> 
<p>比如下图就是模拟向完全二叉树中加入元素&#xff0c;可以发现&#xff0c;新加入元素总是优先供给左子树&#xff0c;左子树满了&#xff0c;再考虑右子树。</p> 
<p><img alt="" height="291" src="https://img-blog.csdnimg.cn/2bd106cde7c74cbc8806b159d6047efe.png" width="1200" /></p> 
<p></p> 
<p>因为上面这个特性&#xff0c;完全二叉树可以用数组模拟&#xff0c;数组元素满足如下规律&#xff1a;</p> 
<p>arr[i] 的左孩子是 arr[2*i&#43;1] &#xff0c;右孩子是 arr[2*i &#43; 2]。&#xff08;i从0开始计数&#xff09;</p> 
<p>比如数组 arr &#61; [1,2,3,4]&#xff0c;则对应完全二叉树如下</p> 
<p><img alt="" height="272" src="https://img-blog.csdnimg.cn/05e5494287844b36b99f412d2f4b7e65.png" width="349" /></p> 
<p></p> 
<p>了解了完全二叉树和数组的关系后&#xff0c;本题的解决就非常简单了&#xff0c;不需要实现一个完全二叉树的数据结构&#xff0c;直接依赖于数组&#43;深度递归就可以完成完全二叉树的后序遍历。</p> 
<p></p> 
<p>用例的示意图</p> 
<p><img alt="" height="291" src="https://img-blog.csdnimg.cn/0ca84e7dfe8046a3bd116aeaea3cda92.png" width="506" /></p> 
<p>因此用例的后序遍历是&#xff1a;左-右-根&#xff0c;即2,3,1</p> 
<p></p> 
<p>由于题目要求不能遍历叶子节点&#xff0c;因此我们需要判定什么节点是叶子</p> 
<p><img alt="" height="258" src="https://img-blog.csdnimg.cn/236513527fcc4f4cae5ef05e1bccacf0.png" width="450" /></p> 
<p><img alt="" height="257" src="https://img-blog.csdnimg.cn/0d149a4de43f4cd4bec2949364c96cfc.png" width="386" /></p> 
<p>如上面两个图所示&#xff0c;只要该节点有左孩子&#xff0c;那么该节点就不是叶子&#xff0c;比如2节点。</p> 
<p></p> 
<p>因此我们只需要从数组第i个元素开始深度递归&#xff0c;递归逻辑&#xff1a;</p> 
<p>假设第i个元素为根&#xff0c;那么它的左孩子是 arr[2*i&#43;1]&#xff0c;右孩子是arr[2*i&#43;2]&#xff1a;</p> 
<ol><li>如果左孩子不为空&#xff0c;则说明第i个元素不是叶子&#xff0c;因此继续递归其左孩子&#xff0c;即将左孩子当成新的根来递归。如果递归到本身是叶子节点&#xff0c;则停止递归。</li><li>如果右孩子也不为空&#xff0c;则根据后序遍历原则&#xff0c;还要对右孩子进行递归&#xff0c;即将右孩子也当成根。如果递归到本身是叶子节点&#xff0c;则停止递归。</li><li>打印arr[i]</li></ol> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on(&#34;line&#34;, (line) &#61;&gt; {
  const arr &#61; line.split(&#34; &#34;);
  console.log(getResult(arr));
});

function getResult(arr) {
  if (arr.length &#61;&#61;&#61; 1) return arr[0];

  const res &#61; [];
  dfs(arr, 0, res);

  return res.join(&#34; &#34;);
}

function dfs(arr, root, res) {
  let left &#61; 2 * root &#43; 1;
  let right &#61; 2 * root &#43; 2;

  if (arr[left]) {
    dfs(arr, left, res);
    if (arr[right]) dfs(arr, right, res);
    res.push(arr[root]);
  }
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  // 输入获取
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    Integer[] arr &#61;
        Arrays.stream(sc.nextLine().split(&#34; &#34;)).map(Integer::parseInt).toArray(Integer[]::new);

    System.out.println(getResult(arr));
  }

  // 算法入口
  public static String getResult(Integer[] arr) {
    if (arr.length &#61;&#61; 1) return arr[0] &#43; &#34;&#34;;

    ArrayList&lt;Integer&gt; res &#61; new ArrayList&lt;&gt;();
    dfs(arr, 0, res);

    StringJoiner sj &#61; new StringJoiner(&#34; &#34;);
    for (Integer re : res) {
      sj.add(re &#43; &#34;&#34;);
    }

    return sj.toString();
  }

  public static void dfs(Integer[] arr, int root, ArrayList&lt;Integer&gt; res) {
    int left &#61; root * 2 &#43; 1;
    int right &#61; root * 2 &#43; 2;

    if (arr.length &gt; left) {
      dfs(arr, left, res);
      if (arr.length &gt; right) dfs(arr, right, res);
      res.add(arr[root]);
    }
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
arr &#61; list(map(int, input().split()))


def dfs(arr, root, res):
    left &#61; root * 2 &#43; 1
    right &#61; root * 2 &#43; 2

    if len(arr) &gt; left:
        dfs(arr, left, res)
        if len(arr) &gt; right:
            dfs(arr, right, res)
        res.append(arr[root])


# 算法入口
def getResult():
    if len(arr) &#61;&#61; 1:
        return arr[0]

    res &#61; []
    dfs(arr, 0, res)

    return &#34; &#34;.join(map(str, res))


# 算法调用
print(getResult())
</code></pre> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;string.h&gt;

#define MAX_SIZE 1000

// 一个以顺序储存结构存储整数值的完全二叉树序列
int nums[MAX_SIZE];
int nums_size &#61; 0;

// 非叶子节点后序遍历序列
int non_leafs[MAX_SIZE];
int non_leafs_size &#61; 0;

// 记录题解
char res[10000];

void dfs(int root);

int main() {
    while (scanf(&#34;%d&#34;, &amp;nums[nums_size&#43;&#43;])) {
        if (getchar() !&#61; &#39; &#39;) break;
    }

    if (nums_size &#61;&#61; 1) {
        // 只有一个节点时&#xff0c;直接输出
        printf(&#34;%d\n&#34;, nums[0]);
    } else {
        // 按照后序遍历规则&#xff0c;递归完全二叉树
        dfs(0);

        // 打印非叶子节点的后序遍历
        for (int i &#61; 0; i &lt; non_leafs_size; i&#43;&#43;) {
            char tmp[100];
            sprintf(tmp, &#34;%d&#34;, non_leafs[i]);

            strcat(res, tmp);
            strcat(res, &#34; &#34;);
        }

        // 按照前面拼接逻辑&#xff0c;res末尾会多拼接一个空格
        res[strlen(res) - 1] &#61; &#39;\0&#39;;

        puts(res);
    }

    return 0;
}

void dfs(int root) {
    int left &#61; root * 2 &#43; 1;
    int right &#61; root * 2 &#43; 2;

    // 左&#xff1a;如果左孩子不为空&#xff0c;则说明第i个元素不是叶子&#xff0c;因此继续递归其左孩子&#xff0c;即将左孩子当成新的根来递归
    if (nums_size &gt; left) {
        dfs(left);
        // 右&#xff1a;如果右孩子也不为空&#xff0c;则根据后序遍历原则&#xff0c;还要对右孩子进行递归
        if (nums_size &gt; right) dfs(right);
        // 根
        non_leafs[non_leafs_size&#43;&#43;] &#61; nums[root];
    }
}</code></pre> 
<p> </p>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>